#include<tools_heap.h>
#include<stdlib.h>


#define RIGHT_CHILD(x) (2*(x+1))
#define LEFT_CHILD(x) (2*x+1)
#define PARENT(x) ((x-1)/2)

static inline void swap(CHeap*ch,int index1,int index2)
{
    void * temp=ch->values[index1];
    ch->values[index1]=ch->values[index2];
    ch->values[index2]=temp;
}

static void adjust_min(CHeap*ch,int index)
{
    int left=LEFT_CHILD(index),right=left+1;
    if(left>=ch->size)
    {
        return;
    }
    int change=left;
    if(right<ch->size&&ch->comp(ch->values[right],
        ch->values[left])<0)
    {
        change=right; 
    }    
    if(ch->comp(ch->values[change],ch->values[index])<0)
    {
        swap(ch,change,index);
        adjust_min(ch,change);
    } 
}

void make_min_cheapi(CHeap* ch,int index)
{
    if(index>=ch->size)
    {return ;}
    int left=LEFT_CHILD(index),right=left+1;
    make_min_cheapi(ch,left);
    make_min_cheapi(ch,right);
    adjust_min(ch,index);
}

static void make_min_cheap(CHeap*ch)
{
    for(int i=ch->size/2-1;i>=0;i--)
    {adjust_min(ch,i);}
}
static void adjust_max(CHeap*ch,int index)
{
    int left=LEFT_CHILD(index),right=left+1;
    if(left>=ch->size){return;}
    int change=left;
    if(right<ch->size&&ch->comp(ch->values[right],ch->values[left])>0)
    {change=right; }    
    if(ch->comp(ch->values[change],ch->values[index])>0)
    {
        swap(ch,change,index);
        adjust_max(ch,change);
    } 
}
void make_max_cheapi(CHeap* ch,int index)
{
    if(index>=ch->size){return ;}
    int left=LEFT_CHILD(index),right=left+1;
    make_max_cheapi(ch,left);
    make_max_cheapi(ch,right);
    adjust_max(ch,index);
}
static void make_max_cheap(CHeap*ch)
{
    for(int i=ch->size/2-1;i>=0;i--){adjust_max(ch,i);}
}
void make_cheap(CHeap*ch)
{
    if(ch->mark==0){make_min_cheap(ch);}
    else{make_max_cheap(ch);}
}
void* pop_cheap(CHeap*ch)
{
    if(ch->size<=0){return NULL;}
    ch->size--;
    void* re=ch->values[0];
    ch->values[0]=ch->values[ch->size];
    ch->values[ch->size]=NULL;
    if(ch->mark==0)
    {adjust_min(ch,0);}
    else{adjust_max(ch,0);}
    return re;
}

static void adjust_parent_min(CHeap*ch,int index)
{
    int pa=PARENT(index);
    if(pa>=0&&ch->comp(ch->values[pa],ch->values[index])>0)
    {
        swap(ch,index,pa);
        adjust_parent_min(ch,pa);
    } 
}
static void adjust_parent_max(CHeap*ch,int index)
{
    int pa=PARENT(index);
    if(pa>=0&&ch->comp(ch->values[pa], ch->values[index])<0)
    {
        swap(ch,index,pa);
        adjust_parent_max(ch,pa);
    } 
}
int insert_cheap(CHeap*ch,void* value)
{
    if(ch->size>=ch->max_size){
        ch->max_size+=90000;
        ch->values=(void**)realloc(ch->values,sizeof(void*)*(ch->max_size));
    }
    ch->values[ch->size]=value;
    //memcpy(((char*)ch->values)+ch->width*ch->size,value,ch->width); 
    ch->mark==0?adjust_parent_min(ch,ch->size):adjust_parent_max(ch,ch->size);
    ch->size++;
    return 1;
}
